In addition to such well known processes where values comprising labels are assigned to patterns of one form or another and output as responses by a recogniser, there are also many other processes in which patterns are recognised and values are output as responses. Two examples of such processes are for example echo cancellation and signal filtering, though hitherto such processes have not been considered as pattern recognition problems.
In all such processes though patterns are input, and a response is output and whilst the present invention is particularly suitable for use with recognition processes which also involve cancellation processes it may be adapted for other recognition processes where its properties may be used to advantage. In order to discuss the present invention more readily, particular reference will be made to the field of echo cancellation.
Echo cancellers are used in telephone circuits to suppress echoes received from a circuit by a station which emanate from signals transmitted into the circuit by the same station. Echoes result from a variety of causes for example slight mismatches in four to two wire hybrids and from accoustic feedback in the distant stations handset. Normally such echoes are not noticeable but with International calls, where the echo may be delayed by more than a few tens of milliseconds, they can be annoying. In order to maintain duplex operation an echo canceller is required which can model the response of any feedback path. Since different feedback paths and different hybrids will have different characteristics the canceller must be adaptive to be useful in any circuit.
Three main forms of filters/echo cancellers are known. In the first, known as an F.I.R. canceller (Finite Impulse Response), the input signal is convolved with the impulse response of the line to form an instantaneous echo estimate. In the UK the maximum echo delay encountered is about 32 ms and with an 8 kHz sampling rate a 256 tap shift register would be needed to hold the relevant history of the input signal whose echo is to be estimated. In order to estimate such an echo and update the response the canceller would need to perform 512 multiplications and 512 additions within the 125?s period between samples. To do this is expensive in terms of the high speed devices and fast memory required.
A second form of echo canceller uses the entire contents of the signal history shift register to address a large memory. Each possible previous form of the signal thus has a corresponding memory location and in each of these locations data is stored which comprises an estimate of the corresponding echo response for the particular signal history in the signal history shift register. However, if 8 bit words are used with the 240 tap shift register, which would be required as described above, the signal history shift register will have 1920 locations and thus the random access memory for storing the corresponding echo estimates will required 2.sup.1920 8 bit word locations. Such an amount of memory is clearly impracticable to implement and the only practical cancellers of this type use a signal history shift register which is considerably smaller. The advantages of such a system are that no multiplications or additions are required and that since each input signal accesses a different memory location many non-linearities in the feedback path can be cancelled. However, the adaption times of such cancellers is long and in any event due to the constraints on memory size such cancellers are only practicable for use in systems where the number of transmitted symbols is small and the echo path short. Such systems are therefore unsuitable for speech signals.
A third form of echo canceller uses the contents of stages of an input shift register each containing a digital word of a signal to provide the addresses for a plurality of random access memories, each stage and thus word providing the address for a corresponding RAM. The contents of the RAM locations addressed thus are then summed to provide an echo estimate which can be updated. However such cancellers are only able to cope with amplitude dependant instantaneous non-linearities.